package bTree.LeetCode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 分割回文串 {
    List<List<String>>res=new LinkedList<>();
    List<String>temp=new ArrayList<>();
    public List<List<String>> partition(String s) {
        Backtracking(s,0,new StringBuilder());
        return res;
    }


    private void Backtracking(String s, int startindex,StringBuilder sb) {
        if(startindex==s.length()){
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i=startindex;i<s.length();i++){
            //不能直接拼接，要stringbiulder来过度用
            sb.append(s.charAt(i));
            if(ifhuiwen(sb.toString())){
               temp.add(sb.toString());
               Backtracking(s,i+1,new StringBuilder());
               temp.remove(temp.size()-1);
            }
        }
    }

    private boolean ifhuiwen(String s){
        int left=0,right=s.length()-1;
        for(int i=0;i<s.length();i++){
            if(s.charAt(left)!=s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}